package cn.qyd.kaoshi;

import java.util.ArrayList;

/**
 * @author 邱运铎
 * t贪吃和馋嘴
 * 1. 贪吃拿 10 馋嘴拿 5
 * 2， 贪吃拿 2 馋嘴拿 8
 * 3， 贪吃拿 7
 * @date 2024-03-26 14:15
 */
public class EatPizza01 {
    private static int[] pizza = new int[]{8,2,10,5,7};
    private static ArrayList<String> result = new ArrayList<>();
    private static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) {
        String word = "Hello World!";
        int len = pizza.length;
        for (int i = 0; i < len; i++) {
            sb.append(i);
            dispatchPizza(i -1, i + 1);
            sb.deleteCharAt(sb.length() - 1);
        }
        System.out.println(result);
    }

    public static void dispatchPizza(int left, int right) {
        left = left < 0 ? pizza.length - 1  : left;
        right = right >= pizza.length ? 0 : right;
//        System.out.println("----刚进入方法------");
//        System.out.println(Arrays.toString(pizza));
//        System.out.println(sb);
//        System.out.println(left + "-----" + right);
//        System.out.println("----刚进入方法------");
        //因为馋嘴必定是选择当前缺口左右两边最大的那个，比较那边大，让边界向那边移动一位，表示被馋嘴吃掉
        if (pizza[left] > pizza[right]) {
            left = left - 1 < 0 ? pizza.length - 1 : left - 1;
        } else {
            right = right + 1 >= pizza.length ? 0 : right + 1;
        }
//        System.out.println("馋嘴吃完后的边界： " + left + "-----" + right);
        //如果被馋嘴吃掉后，left和right相等，表明剩下最后一块，直接让贪吃吃掉，并返回。
        if (left == right) {
            sb.append(left);
            result.add(sb.toString());
//            System.out.println("回溯了， 当前str--" + sb);
            sb.deleteCharAt(sb.length() - 1);
            return;
        }
        //让贪吃吃掉左边界的披萨
        sb.append(left);
        left--;
        dispatchPizza(left,right);
        left++;
        sb.deleteCharAt(sb.length()-1);
//        System.out.println("左子树递归后回溯的边界： " + left + "-----" + right);
//        System.out.println("左子树递归后回溯的str： " + sb);
        //让贪吃吃掉右边界的披萨
        sb.append(right);
        right++;
        dispatchPizza(left,right);
        right--;
        sb.deleteCharAt(sb.length() - 1);
//        System.out.println("右子树递归后回溯的边界： " + left + "-----" + right);
//        System.out.println("右子树递归后回溯的str： " + sb);

    }
}

